package cn.zifangsky.graph;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.queue.Queue;
import cn.zifangsky.stack.LinkStack;
import cn.zifangsky.stack.Stack;

import java.util.List;
import java.util.function.Consumer;

/**
 * 拓扑排序
 * <p>定义：在一个有向无环图（DAG）中，对DAG的顶点进行排序，使得对每一条有向边(u, v)，均有u（在排序记录中）比v先出现。
 * 亦可理解为对某点v而言，只有当v的所有源点均出现了，v才能出现。</p>
 *
 * @author zifangsky
 * @date 2019/1/23
 * @since 1.0.0
 */
public class TopologicalSort {

    private GraphList graphList;

    public TopologicalSort(GraphList graphList) {
        this.graphList = graphList;
    }


    /**
     * 通过 入度表 求“拓扑排序”
     * <p>实现思路：</p>
     * <ul>1. 找出图中入度为0的顶点，然后将它添加到队列中</ul>
     * <ul>2. 将入度为0的顶点的邻接顶点的入度-1，如果该顶点的入度已经为0，则将它添加到队列中</ul>
     * <ul>3. 最后将顶点依次出队，得到“拓扑排序”</ul>
     * <p>时间复杂度：O(V+E)</p>
     * @author zifangsky
     * @date 2019/1/24 14:16
     * @since 1.0.0
     * @param consumer consumer
     */
    public void sortByDegree(Consumer<String> consumer){
        //图中的顶点数
        int vertexNum = graphList.getVertexNum();
        //所有顶点
        List<String> vertexList = graphList.getVertexList();
        //所有顶点信息
        GraphList.VertexNode[] list = graphList.getList();
        //定义一个索引队列
        Queue<Integer> indexQueue = new LinkQueue<>();
        //定义一个顶点名称队列
        Queue<String> nameQueue = new LinkQueue<>();

        //1. 得到图中每个顶点构成的入度表
        int[] inDegreeArray = this.getInDegreeArray(vertexNum, vertexList, list);

        //2. 遍历入度表，将入度为0的顶点添加到队列中
        for(int i = 0; i < inDegreeArray.length; i++){
            if(inDegreeArray[i] == 0){
                indexQueue.push(i);
            }
        }

        //3. 将顶点依次出队，更新其邻接顶点的入度
        while (!indexQueue.isEmpty()){
            //顶点索引
            Integer vertexIndex = indexQueue.pop();
            //顶点名称
            String vertexName = vertexList.get(vertexIndex);
            GraphList.VertexNode current = list[vertexIndex];
            //将顶点名称添加到结果队列中
            nameQueue.push(vertexName);

            //邻接顶点所在链表
            GraphList.EdgeNode temp = current.getEdgeNode();
            while (temp != null){
                //3.1 相邻顶点的索引
                int index = vertexList.indexOf(temp.getEndVertex());
                //3.2 该顶点入度-1
                inDegreeArray[index]--;
                //3.3 如果入度为0，则将其添加到队列中
                if(inDegreeArray[index] == 0){
                    indexQueue.push(index);
                }

                temp = temp.next;
            }
        }

        //4. 如果最后队列中顶点数等于所有顶点，则说明存在“拓扑排序”
        if(nameQueue.size() == vertexNum){
            //依次出栈，即得到“拓扑排序”的结果
            while (!nameQueue.isEmpty()){
                consumer.accept(nameQueue.pop());
            }
        }else {
            consumer.accept("当前图中不存在“拓扑排序”");
        }
    }

    /**
     * 获取图中每个顶点的入度情况
     * @author zifangsky
     * @date 2019/1/24 14:51
     * @since 1.0.0
     * @return java.lang.String[]
     */
    private int[] getInDegreeArray(int vertexNum, List<String> vertexList, GraphList.VertexNode[] list){
        //入度表
        int[] inDegreeArray = new int[vertexNum];

        for(GraphList.VertexNode current : list){
            GraphList.EdgeNode temp = current.getEdgeNode();
            while (temp != null){
                //相邻顶点的索引
                int index = vertexList.indexOf(temp.getEndVertex());
                //该顶点入度+1
                inDegreeArray[index]++;
                temp = temp.next;
            }
        }

        return inDegreeArray;
    }


    /**
     * 通过深度优先搜索求“拓扑排序”
     * <p>实现思路：</p>
     * <ul>1. 使用DFS遍历</ul>
     * <ul>2. 如果当前顶点没有被遍历过，且其所有邻接点都已入栈，那么就将它添加到栈中</ul>
     * <ul>3. 依次出栈，得到“拓扑排序”</ul>
     * <p>时间复杂度：O(V+E)</p>
     * @author zifangsky
     * @date 2019/1/23 18:04
     * @since 1.0.0
     * @param consumer consumer
     */
    public void sortByDFS(Consumer<String> consumer){
        //图中的顶点数
        int vertexNum = graphList.getVertexNum();
        //定义一个栈
        Stack<String> stack = new LinkStack<>();

        //标识每个顶点是否被访问
        boolean[] visited = new boolean[vertexNum];
        for(int i = 0; i < vertexNum; i++){
            visited[i] = false;
        }

        //1. dfs遍历图中顶点
        for(int i = 0; i < vertexNum; i++){
            if(!visited[i]){
                this.dfs(visited, i, stack);
            }
        }

        //2. 如果最后栈中顶点数等于所有顶点，则说明存在“拓扑排序”
        if(stack.size() == vertexNum){
            //依次出栈，即得到“拓扑排序”的结果
            while (!stack.isEmpty()){
                consumer.accept(stack.pop());
            }
        }else {
            consumer.accept("当前图中不存在“拓扑排序”");
        }
    }

    /**
     * DFS（深度优先搜索）
     * @param visited 标识每个顶点是否被访问
     * @param vertexIndex 顶点索引
     * @param stack 存储顶点
     */
    private void dfs(boolean[] visited, int vertexIndex, Stack<String> stack){
        //所有顶点
        List<String> vertexList = graphList.getVertexList();
        //当前的顶点信息
        GraphList.VertexNode current = graphList.getList()[vertexIndex];

        //1. 标识置为——已访问
        visited[vertexIndex] = true;

        //2. 遍历当前顶点的相邻顶点
        GraphList.EdgeNode temp = current.getEdgeNode();
        while (temp != null){
            //相邻顶点的索引
            int index = vertexList.indexOf(temp.getEndVertex());
            if(!visited[index]){
                this.dfs(visited, index, stack);
            }
            temp = temp.next;
        }

        //当前顶点的邻接顶点已经被访问过，且其所有邻接顶点都已入栈，那么就将它添加到栈中
        if(checkInStack(current.getEdgeNode(), stack)){
            stack.push(current.getName());
        }
    }

    /**
     * 检查某个顶点的所有邻接顶点是否都已入栈
     */
    private boolean checkInStack(GraphList.EdgeNode edgeNode, Stack<String> stack){
        while (edgeNode != null){
            if(!stack.contains(edgeNode.getEndVertex())){
                return false;
            }
            edgeNode = edgeNode.next;
        }

        return true;
    }

}
